package com.easy.carl.algorithm.tree;

import com.easy.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths257 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res= new ArrayList<>();
        if (root==null) {
            return res;
        }
        List<Integer> path=new ArrayList<>();
        backTrack(res,root,path);
        return res;
    }
    private void backTrack(List<String> res,TreeNode cur,List<Integer> path){
        path.add(cur.val);
        //终止条件,叶子节点
        if (cur.left==null&&cur.right==null){
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < path.size(); i++) {
                sb.append(path.get(i).intValue());
                if (i!=path.size()-1){
                    sb.append("->");
                }
            }
            res.add(sb.toString());
           return;
        }
        if (cur.left!=null){
            backTrack(res,cur.left,path);
            //回溯
            path.remove(path.size()-1);
        }
        if (cur.right!=null){
            backTrack(res,cur.right,path);
            //回溯
            path.remove(path.size()-1);
        }
    }
}
